//Main Compression Program
#include "huff.h"



/********************************************
*  readFile takes in an array and File path
*  then reads in the file character by 
*  character.  This then stores the amount
*  of each character to the charCount Array
*  in an index realted to its ASCII value.
*  It also causes termination if file is not
*  found
*
*   Author: Michael Sickles
********************************************/
void  readFile(huffTree** pointer,char* fpath){
    FILE *fp;
    fp = fopen(fpath,"r");
    char c;
    if (fp == NULL){
        /*return Error if File not Found*/
        exit(8);
    }
    /*Get character until End of File, Store 
      How many times it shows up */
    c=fgetc(fp);
    while(c != EOF){
        /*Add one to weight and Place at location of 
          ascii value in array of nodes */
        pointer[(int)c]->weight +=1;
        pointer[(int)c]->character = c;
        c=fgetc(fp);
    }
    fclose(fp);
}

/*************************************************
*
* Simple function to find how many unique characters
* show up in the charCount array.  
*
*  Author: Michael Sickles
*
*************************************************/
int countArray(huffTree** pointer){
    int i =0;
    int size = 0;
    while(i<256){
        //if something has a weight, add add 1 to size
        if(pointer[i]->weight > 0){
            size++;
        }
        i++;
    }
    return size;
}
/**************************************************
* Dequeue removes an element from the queue and 
* returns and huffTree node.
*
*  Author: Michael Sickles, John Jachna
*
***********************************************/
huffTree* dequeue(pqueue* q){
     huffTree* node;
     //create node
     node = (huffTree*)malloc(sizeof(huffTree));
     if(q->front != -1 && q->rear != -1){
         //make node to the front of queue
         node = q->nodes[q->front];
         //move the front
         q->front = q->front + 1;
         //wrap around if greater than size
         if(q->front > q->size-1)q->front = 0;
         //return created node
         return node;

    }
exit(1); 

}
/******************************************************************
*
*  This function takes an huffTree element and based on its priority
*  it inserts it into the queue.  A lower weight has a higher 
*  priority. This is done by a circular queue
*
*  Authors: Michael Sickles, John Jachna
*
********************************************************************/
void enqueue(pqueue* q, huffTree* node){
    int i,j;
    huffTree* temp;
    temp = (huffTree*)malloc(sizeof(huffTree));
    //if its empty, just create the node
    if(q->front== -1 && q->rear==-1){
        q->front=0;
        q->rear=0;
        q->nodes[q->rear]=node;
    }else{
    //else go through the queue and compare priorities
        //make the rear one higher
        q->rear=q->rear+1;
        //if rear is equal to size, wrap to front of array
        if(q->rear>=q->size)q->rear=q->rear%q->size;
        q->nodes[q->rear]=node;
        i=q->rear;
        j=i-1;
        //Wrap around if j ends up negative
        if(j<0)j=q->size-1;
        while(i!=q->front){
            //while we have not reached the front of queue
            if(q->nodes[i]->weight < q->nodes[j]->weight){
                //if weight is less, move toward front
                temp = q->nodes[i];
                q->nodes[i]=q->nodes[j];
                q->nodes[j]=temp;
            }
            i--;
            j--;
            //wrap around if negative value index
            if(i<0)i=q->size-1;
            if(j<0)j=q->size-1;
        }
    }    
    

}

/*******************************************************
*
*  createTree takes in your queue and forms it into a 
*  huff tree. It returns the completed Tree
*
*  Author: Michael Sickles
*
******************************************************/
huffTree* createTree(pqueue* q){
    huffTree* root; 
   //int i; 
    while(q->front != q->rear){
          //remove low priority from queue
        // then make children of root
          root = (huffTree*)malloc(sizeof(huffTree));
          root->left = dequeue(q);
          root->right = dequeue(q);
          //give root its weight
          root->weight = root->left->weight + root->right->weight;

        // put the root node  back in the queue
          enqueue(q,root);
    }
    //return Final node
    return dequeue(q);

}



/******************************************************
*
* This function takes in a huff tree and builds its
* huff codes stored in the 256 character array.
*
* Author: Michael Sickles
*
****************************************************/
void buildCode(huffTree* tree,char* string,huffTree** pointer){
    char* buff1;//buffer1 to store left traversal
    char* buff2;//buffer2 to store right traversal
    int ret;//hold returns
    int ret2;
    //assuming worst case 30 bit sequence
    buff1 = malloc(100*sizeof(char));
    buff2 = malloc(100*sizeof(char));
    if(tree->left == NULL && tree->right == NULL && pointer[(int)tree->character]->code == NULL){//if both children are null, youre at a leaf
        pointer[(int)tree->character]->code = string;//set pointer of ascii array to hold the corresponding code
    }else{
        //cat strings
         ret = sprintf(buff1,"%s0",string);
        ret2 = sprintf(buff2,"%s1",string);
        //traverse the tree
        if(tree->left != NULL)buildCode(tree->left,buff1,pointer);
        if(tree->right != NULL)buildCode(tree->right,buff2,pointer);
    }
}


/********************************************************
*
* Create Header takes in the array of pointers and 
*
* Writes to a file a bunch of codes to be interpreted later
*
* Author: Michael Sickles
********************************************************/
void createHeader(huffTree** pointer,char* filename,long amount){
    FILE *fp;
    int i;
    //open file
    fp = fopen(filename,"w+");
    //opening header
    fprintf(fp,"--huff--\n");
    for(i=0;i<256;i++){
            //if a value has a code print that charcter followed by bit sequence size followed by code
        if(pointer[i]->weight >0){
            fprintf(fp,"%c%s\n",pointer[i]->character,pointer[i]->code);
            //printf("H| Char: %c Len: %d code:%s\n",pointer[i]->character,(int)strlen(pointer[i]->code),pointer[i]->code);
    }}
    //close off header
    fprintf(fp,"\n-%ld\n",amount);
    //store file
fclose(fp);
}


long encode(huffTree** pointer,char* filein,char* fileout){
    FILE *fin;
    FILE *fout;
    //int buff[8];
    char c;
    long amount=0;
    //open files
    fin = fopen(filein,"r");
    fout = fopen(fileout,"a");

    c=fgetc(fin);
    while(c != EOF){
        fprintf(fout,"%s",pointer[(int)c]->code);
        amount += (long)strlen(pointer[(int)c]->code);
        c = fgetc(fin);
    
    }



   fclose(fin);
   fclose(fout);
   return amount;
}

void encodeToFile(char* output)
{
    char buffer[8];

    FILE* fin;
    FILE* fout;
    int sum;
    char c;

    int i,j;

    fin = fopen("htemp.temp", "r");
    fout = fopen(output, "a");
    
    while(fgets(buffer, 9, fin) != NULL)
    {
       // printf("buffer: %s\n",buffer);
       // fgets(buffer, 9, fin);
        j = 128;
        sum=0;
        for(i = 0; i < 8; i++)
        {
            if(buffer[i]=='\0')buffer[i]='0';
         //   printf("Buffer: %c\n",buffer[i]);
            if(buffer[i]=='1')sum += j;
            
            j /= 2;
        }
        
        //temp = buffer[6];
        //temp2 = atoi(&temp);
        //printf("7: %d 6: %d 5: %d 4: %d 3:%d 2: %d 1: %d 0:%d\n",atoi(&buffer[7]),2*temp2,4*atoi(&buffer[5]),8*atoi(&buffer[4]),16*atoi(&buffer[3]),32*atoi(&buffer[2]),64*atoi(&buffer[1]),128*atoi(&buffer[0]));
//        sum = atoi(&buffer[7]) + 2*atoi(&buffer[6]) + 4*atoi(&buffer[5]) + 8*atoi(&buffer[4]) + 16*atoi(&buffer[3]) + 32*atoi(&buffer[2]) + 64*atoi(&buffer[1]) + 128*atoi(&buffer[0]);
       // printf("C is %c and i is %d\n",sum,sum);    
        c = sum;
        fputc(c, fout);
    }
    
    remove("htemp.temp");

    fclose(fin);
    fclose(fout);
}

/*------------------------------------------------------*/


 
int main(int argc, char *argv[]){
    huffTree* charCount[256]; //holds ascii array
    huffTree** pointer = charCount; //makes it an array of pointers
    pqueue q;//priority queue
    huffTree *node,*tree; //temp node and root
    char *filename;//file name in
    int size,ret,i;
    char* fnew;
    long amount;
    
    //Malloc space for the Tree
    tree = (huffTree*)malloc(sizeof(huffTree));
    
    //Make array of nodes
    for(i=0;i<256;i++){
        node = (huffTree*)malloc(sizeof(huffTree));
        //make defaults
        node -> weight = 0;
        node -> left = NULL;
        node -> right = NULL;
        //30 is max bit length
        node->code = malloc(30*sizeof(char));
        node -> code = NULL;
        //save that node Mr. President
        pointer[i]=node;
    }
    if(argc != 2)
     {
         printf("Usage: ./huff <filename>\n");
        return ERROR;
      }
//load in filename   
    filename = argv[1];

    //make space for new file name
    fnew = malloc((strlen(filename)+5)*sizeof(char));
    //Append .huff
    ret = sprintf(fnew,"%s.huff",filename);
    //read in unique characters
    readFile(pointer,filename);

    //Count Unique
    size = countArray(pointer);

    //Build the queue
    q.forest = malloc(size*sizeof(huffTree));
    q.nodes = malloc(size*sizeof(huffTree));
    *q.nodes = q.forest;
    q.size=size;
    q.front = -1;
    q.rear = -1;
    for(i=0;i<256;i++){
        //if it has weight, insert node in the queue
        if(pointer[i]->weight > 0){
            enqueue(&q,pointer[i]);
        }
     }

    //build huff Tree
    tree = createTree(&q);

    //Translate it to codes
    buildCode(tree,"",pointer);
//for(i=0;i<256;i++)printf("Character: %c, Code: %s Weight: %d\n",pointer[i]->character,pointer[i]->code,pointer[i]->weight);
    amount = encode(pointer,filename,"htemp.temp");
    //Create header in new file
    createHeader(pointer,fnew,amount);
    
    encodeToFile(fnew);
    //WINNING
    return OK;

    }
